巅峰赛25题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 兔子之谜 普及- T2 求职 普及/提高- T3 午枫的LCA 普及+/提高 T4 太空传送 普及+/提高 T5 括号序列 普及+/提高 T6 博弈 提高+/省选-
T1 兔子之谜
题目大意
有 nnn 只兔子，每只兔子有两个耳朵，每个耳朵会指向上下左右四个方向之一，每个方向代表四进制中的一个数。他们从左到右排成一排一共有 2n2n2n 个耳朵，按顺序给出所有耳朵的方向，求耳朵隐含的四进制数转化为十进制数是多少。
题目思路
根据题意先模拟得到四进制数，然后再转换成十进制数即可。四进制转十进制可类比二进制转十进制。需要注意本题需要使用 long long 数据类型存答案。
参考代码
T2 求职
题目大意
有 nnn 家公司和 mmm 为求职者，每家公司有两个能力要求，每位求职者也有两个能力值，求职者只有都满足这两个要求才可以通过面试，求每位求职者可以通过多少家公司的面试。
题目思路
我们可以把两个能力值看成一个二维的坐标，那么对于某家公司的要求 (a,b)(a,b)(a,b) ，能力值为 (x,y)(x,y)(x,y) 的求职者只有同时满足 x≥ax\geq ax≥a 且 y≥by\geq by≥b 才可以通过面试，即 (x,y)(x,y)(x,y) 在左上角为 (a,b)(a,b)(a,b) 到右下角为 (1000,1000)(1000,1000)(1000,1000) 的范围内即可满足条件。
所以我们不妨用二维差分+前缀和的思想来求出每位求职者可以通过面试的公司数量，对每家公司的要求 (a,b)(a,b)(a,b) 点上的差分数组加一，最后求出前缀和，O(1)O(1)O(1) 查询每位求职者的可通过面试数量。
时间复杂度 O(106)O(10^6)O(106)
参考代码
T3 午枫的LCA
题目大意
有两颗不同的树 AAA 和 树 BBB ，每个点都有一个权值，现在两棵树都有 mmm 个节点被标记且被标记的节点编号相同。询问这 mmm 个节点，对于每个被标记节点 xix_ixi ，如果只有这个节点的标记删除，剩下 m−1m-1m−1 个标记节点在树 AAA 中的最近公共祖先的权值是否大于树 BBB 中的最近公共祖先的权值。
题目思路
不难发现，若删****x_ixi 节点的标记，那么要求的 LCALCALCA 是
lca(x1,x2,…,xi−1,xi+1,…,xn−1,xn)=lca(lca(x1,x2,…,xi−1),lca(xi+1,…,xn−1,xn))lca(x_1,x_2,\dots,x_{i-1},x_{i+1},\dots,x_{n-1},x_n)\\ =lca(lca(x_1,x_2,\dots,x_{i-1}),lca(x_{i+1},\dots,x_{n-1},x_n)) lca(x1 ,x2 ,…,xi−1 ,xi+1 ,…,xn−1 ,xn )=lca(lca(x1 ,x2 ,…,xi−1 ),lca(xi+1 ,…,xn−1 ,xn ))
所以我们可以预处理 mmm 个标记节点的前缀 LCALCALCA 和后缀 LCALCALCA ，然后枚举删除标记的节点再求一遍 LCALCALCA ，然后比较两棵树上 LCALCALCA 的权值即可。
时间复杂度 O((n+k)logn)O((n+k)logn)O((n+k)logn)
参考代码
T4 太空传送
题目大意
两人从 111 号太空站出发，第 iii 个太空站传送范围为 (i,i+ai](i,i+a_i](i,i+ai ] 且等概率传送，求两人使用相同传送次数到达 nnn 号太空站的概率。
题目思路
通过概率DP思想求解。
设 dpi,jdp_{i,j}dpi,j 表示传送了 jjj 次到达 iii 号太空站的概率。
状态转移：dpk,j+1+=dpi,jdp_{k,j+1}+=dp_{i,j}dpk,j+1 +=dpi,j ，其中 i<k≤i+aii<k\leq i+a_ii<k≤i+ai 。如果直接这么转移时间复杂度是 O(n3)O(n^3)O(n3) 。
但不难发现，转移实际上是一段连续的区间，所以我们可以通过差分前缀和优化。
最终答案为 ∑i=1nf(n,i)2\sum_{i=1}^n f(n,i)^2∑i=1n f(n,i)2 。时间复杂度 O(n2)O(n^2)O(n2) 。
参考代码
T5 括号序列
题目大意
求长度为 nnn 的括号序列 aaa 可能是多少个长度为 mmm 的合法括号序列 bbb 的子序列。
题目思路
读题时需要注意的一个点是括号序列 aaa 不一定是合法的，但求的括号序列 bbb 一定是要合法的。
我们可以将 ( 看成权值为 111 ，将 ) 看成权值为 −1-1−1 ，那么一个合法的括号序列需要满足以下条件：
* 序列和为 000 。
* 最小前缀和为不小于 000 。
我们考虑用动态规划解决这个问题。
设 dpi,j,kdp_{i,j,k}dpi,j,k 表示括号序列 bbb 中已经有 iii 个字符，括号序列 aaa 的前 jjj 个字符是括号序列 bbb 的子序列，括号序列 bbb 的权值前缀和为 kkk 。
那么有以下四种转移：
* i+1i+1i+1 位置为 ( ，且 j=nj=nj=n 或 sj+1≠s_{j+1}\nesj+1 = ( ，则 dpi+1,j,k+1+=dpi,j,kdp_{i+1,j,k+1}+=dp_{i,j,k}dpi+1,j,k+1 +=dpi,j,k 。
* i+1i+1i+1 位置为 ( ，且 j<nj<nj<n 且 sj****_{j+1}=sj+1 = ( ，则 dpi+1,j+1,k+1+=dpi,j,kdp_{i+1,j+1,k+1}+=dp_{i,j,k}dpi+1,j+1,k+1 +=dpi,j,k 。
* i+1i+1i+1 位置为 ) ，且 j=nj=nj=n 或 sj+1≠s_{j+1}\nesj+1 = ) ，则 dpi+1,j,k−1+=dpi,j,kdp_{i+1,j,k-1}+=dp_{i,j,k}dpi+1,j,k−1 +=dpi,j,k 。
* i+1i+1i+1 位置为 ) ，且 j<nj<nj<n 且 sj****_{j+1}=sj+1 = ) ，则 dpi+1,j+1,k−1+=dpi,j,kdp_{i+1,j+1,k-1}+=dp_{i,j,k}dpi+1,j+1,k−1 +=dpi,j,k 。
时间复杂度 O(nm2)O(nm^2)O(nm2) 。
参考代码
T6 博弈
题目大意
有 nnn 盘饼干，双方轮流拿取，每次拿完后可以选择是否将剩余饼干合并到别的盘中，若最终无法拿取的人则输掉游戏。给出 qqq 次询问，求出询问区间 [l,r][l,r][l,r] 中有多少子段先手必胜。
题目思路
先考虑固定盘数时双方如何博弈。
若只有 111 盘饼干，先手必胜。
若有 222 盘饼干，谁把某一盘的饼干取完了谁就输了，所以每一盘饼干有一块是不能取的。不妨令 ai=ai−1a_i=a_i-1ai =ai −1 ，这样问题就变成 nimnimnim 游戏问题，也就是说 XORi=lr(ai−1)=0XOR_{i=l}^{r}(a_i-1)=0XORi=lr (ai −1)=0 的话，先手必败，反之先手必胜。
若有 333 盘饼干，先手可以从最多的那盘取出若干饼干，将剩下的局面变成盘数为 222 且上文提到的异或和为 000 的情况，那么先手必胜。
若有 444 盘饼干，谁先将盘数 −1-1−1 谁就输了，所以还是看异或和是否为 000 。
以此类推，不难发现，当堆数为奇数时，先手必胜，否则令 ai=ai−1a_i=a_i-1ai =ai −1 ，看异或和是否为 000 。
所以我们只需要前缀异或，离线查询，用莫队求解。
时间复杂度 O(nn)O(n\sqrt{n})O(nn ) 。
参考代码
